You should do these problems on paper or mentally first, and only THEN check the solution.
This document is review of the notion of scope and local variables in Python and Java, and an explanation of how these relate to (and are explained by!) let expression and lambda expressions.
Definition: A local variable is one defined inside a function, a class, or a statement block; its scope is the part of the program where it may be referred to without error.
Consider the following short Java program, which simply prints out the number 15:
public class ScopeTest {
public static void main(String args[]) {
int x = 5;
System.out.println( x * 2 + x );
}
}
3.1. What is the rule for the scope of x? Draw a vertical line showing the scope of x.
3.2. Ditto for x and y in:
public class ScopeTest {
public static void main(String args[]) {
int y = 2;
int x = 3 * y;
System.out.println(x + y);
}
}
3.3. Ditto for x,y, and z in:
public class ScopeTest {
public static void main(String args[]) {
int x = 3;
int y = x - 2;
int z = 5 * y;
System.out.println( x * y + z );
}
}
3.
3.Local variables also occur in function definitions and statement blocks (statements inside curly braces, perhaps in a loop or conditional). Consider the following:
public class ScopeTest {
public static void main(String args[]) {
int y = 2;
if(y >= 0) {
int x = 3 * y;
System.out.println(x + y);
}
System.out.println("bye!");
}
}
3.4. Show the scope of the variables x and y in this last example.
3.5. Finally, local variables may be created as parameters of functions; show the scope of x, y, and z in this example (remembering that the rule for scope of members of a class is the whole class):
public class ScopeTest {
public static int f(int y) {
System.out.println("hi");
if(y >= 0) {
int z = 5 * y;
return ( x * y + z );
}
System.out.println("there!");
return y;
}
public static int x = 3;
public static void main(String args[]) {
System.out.println( f( x - 2 ) );
System.out.println("bye!");
}
}
Now let us see how this all works in Python... Consider the following Python program (either typed into the interpreter, run from a file, or run from a code cell in a notebook):
x = 5
print( x * 2 + x )
3.6. What is the rule for the scope of x defined at the top level (i.e., not in a function)? Draw a vertical line showing the scope of x.
3.7. Ditto for x and y in:
y = 2
x = 3 * y
print(x + y)
3.8. Ditto for x,y, and z in:
x = 3
y = x - 2
z = 5 * y
print( x * y + z )
Python also has function definitions.
3.9. Show the scope of the variables x and y in this example:
y = 2
def f(x):
print(x + y)
f(3 * y)
3.10. In Python (but not in Java) functions can be defined locally inside other functions; show the scope of x, y, and z in this example:
x = 3
def f(y):
# this is a function g local to f
def g(z):
return x * y + z
return g(5*y)
print( f(3) )
When local variables have the same name in different scopes, we can get a "hole in scope" phenomenon, where the outer definition is hidden by an inner definition, because you when you look for a variable definition, you look outwards from the use to the CLOSEST ENCLOSING DEFINITION.
3.11. Show the scope of the three DIFFERENT variables called x in the following Java program:
public class ScopeTest {
public static int x = 3;
public static int f(int x) {
return x + 1;
}
public static int g(int z) {
int x = z + 1;
return x;
}
public static void main(String args[]) {
System.out.println( f( 2 * x ) );
System.out.println( g( 2 * x ) );
}
}
3.12. Show the scope of the two DIFFERENT variables called x in the following Python program:
x = 3
def f(x):
return x + 1
print( f( 2 * x ) )
Lambda expressions were introduced using Haskell syntax.
Lambda calculus: bound and free variables, reduction rules.
Let us say that a variable x occurs as a bound variable in a lambda expression (\x -> expr), where
"\x ->" is the binding for the variable x, and
the scope of the binding is expr; and a variable y in a lambda expression
which does not occur in the scope of any bound variable is called a free variable.
For the following lambda expressions, circle each free variable, and for each bound variable, draw a line from the occurrence of the variable in the body to the corresponding lambda binding.
3.13. (\y -> (\x -> y x)) y
3.14. (\x -> x y) (\y -> y x)
3.15. (\x -> (\x -> (\y -> x y)) (\z -> (y z) x))
3.16. Draw the abstract syntax tree for the lambda expression in problem 3.13.
3.17. Ditto for 3.14
3.18. Ditto for 3.15
For the following lambda expressions, perform a single step of reduction and show the substitution that was used. Choose the left-most possible reduction.
3.19. (\x -> (\y -> y x)) z
3.20. (\x -> x) ((\x -> x) ((\x -> x) z))
3.21. The lambda expression in problem 3.14.
3.22. (\x -> x (y x)) (\y -> y z)
3.23. (\x -> x (\x -> y x)) z
3.24. (\x -> ((x (\x -> y x)) x) x) y
3.25. (\x -> (x (\y -> y x)) x) z
For the following lambda expressions, reduce the expression step by step (choosing the left-most possible application each time) until no more reductions can be performed.
You won't be expected to do such multiple reductions on Midterm 1.
3.26. (\x -> x (x z)) (\y -> y)
3.27. (\x -> x (x z)) (\y -> z y)
3.28. The lambda expression in 3.20.
3.29. The lambda expression in 3.15
3.30. (\f -> (\x -> f x) ) (\f -> (\y -> f y) )
3.31. (\f -> (\x -> f (f (f x) ) ) ) (\x -> z x)
3.32. (\f -> f (\x -> (\y -> y) ) (\x -> (\y -> x) ) ) (\x -> (\y -> x) ) /
In Haskell you can set up local variables using a let expression. In the next series of problems, we explore this idea and show its correspondence with a certain kind of lambda expression (showing that lambda expressions really are the "assembly language of functional programming").
Recall that the let expression with a single binding has the following syntax:
let <var> = <expression> in <body>
The rule for the scope of the local variable is simple: the scope is the body.
The body can be any expression or even another let expression; here are some examples:
let x = 5 in x * 2 + x
let y = 2 in let x = 3 * y in x + y
let x = 3 in let y = x - 2 in let z = 5 * y in x * y + z
The nesting in the last one is clearer if we add parentheses:
(let x = 2 in (let y = x - 2 in (let z = 9 in x * y + z)) )
--------------------------------------------- body of (let x = ... )
------------------------ body of (let y = ... )
--------- body of (let z = ... )
For the following, first show the scope of the bound variables in the expression, and then calculate its value, doing all beta-reductions first and arithmetic operations last. Show the substitution and how itis applied to the expression.
3.33.
let x = 5 in x * 2 + x,
3.34.
let x = 8 in x - (3 * x),
3.35.
let x = (3 * 2) in (x-1) * x,
3.36.
let y = 2 in let x = 3 * y in x + y
3.37.
let x = 3 in let y = x - 2 in let z = 5 * y in x * y + z
3.38. Now redo the last one, but evaluate any arithmetic expressions as soon as possible:
Now we investigate how let expressions are really "syntactic sugar" for lambda expressions.
3.39. Find a lambda expression which can be reduced in one step and then evaluated to do the exact same thing as
let x = 5 in x * 2 + xShow the lambda expression and then show how it is evaluated.
3.40. Ditto for:
let y = 2 in let x = 3 * y in x * yevaluating any arithmetic expressions as soon as possible.
3.41. Ditto for let x = 3 in let y = x - 2 in let z = 5 * y in x * y + z.
3.42. Ditto for the following let expression:
let x = 3 in let x = 2 * x in x + 1
3.43. Show the scope of the variable y in the let expression in 3.41 and also in its corresponding lambda expression.
3.44. Ditto for the two occurrences of x in the let and lambda expressions in 3.42, showing the "hole in scope" for the outer occurrence.
3.45. Show the correspondence between the Java program in Problem 3.2 and the let expression in Problem 6.14.
3.46. Ditto for the Python program in Problem 3.8.